using System;
using System.Collections.Generic;
using System.Text;

namespace MiniAnimation
{
    /// <summary>
    ///Looping DinamicArray
    /// </summary>
    /// <typeparam name="E"></typeparam>
    class LoopingArray<E>
    {
        private E[] data;
        int first, last;
        int N;
        public LoopingArray(int capacity)
        {
            data = new E[capacity];
            first = 0; last = 0;
            N = 0;
        }
        public LoopingArray() : this(10) { }
        public int Count => N;
        public bool IsEmpty => N == 0;
        public void AddLast(E e)
        {
            if (N == data.Length)
            {
                ResetCapacity(data.Length * 2);
            }
            data[last] = e;
            last = (last + 1) % data.Length;
            N++;
        }
        public E RemoveFirst()
        {
            if (IsEmpty) { throw new InvalidOperationException("Array Empty"); }
            E res = data[first];
            data[first] = default(E);
            first = (first + 1) % data.Length;
            N--;
            if (N == data.Length / 4)
            {
                ResetCapacity(data.Length / 2);
            }
            return res;
        }
        public E GetFirst()
        {
            if (IsEmpty) { throw new InvalidOperationException("Array Empty"); }
            return data[first];

        }
        public E GetAt(int index)
        {
            if (IsEmpty) { throw new InvalidOperationException("Array Empty"); }
            return data[(first + index) % data.Length];
        }
        private void ResetCapacity(int newCapacity)
        {
            E[] newData = new E[newCapacity];
            for (int i = 0; i < N; i++)
            {
                newData[i] = data[(i + first) % data.Length];

            }
            data = newData;
            first = 0;
            last = N;

        }
        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            res.Append("[");
            for (int i = 0; i < N; i++)
            {
                res.Append(data[(i + first) % data.Length].ToString());
                if ((first + i + 1) % data.Length != last)
                {
                    res.Append(",");
                }
            }
            res.Append("]");
            return res.ToString();
        }

    }
    interface IQueue<E>
    {
        int Count { get; }
        bool isEmpty { get; }
        void Enqueue(E e);
        E Dequeue();
        E Peek();


    }
    /// <summary>
    /// 循环数组为底层的  循环队列
    /// </summary>
    /// <typeparam name="E"></typeparam>
    class LoopingQueue<E> : IQueue<E>
    {
        private LoopingArray<E> array;

        public int Count => array.Count;

        public bool isEmpty => array.IsEmpty;

        public LoopingQueue(int capacity)
        {
            array = new LoopingArray<E>(capacity);
        }
        public LoopingQueue()
        {
            array = new LoopingArray<E>();
        }


        public void Enqueue(E e)
        {
            array.AddLast(e);
        }

        public E Dequeue()
        {
            return array.RemoveFirst();
        }

        public E Peek()
        {
            if (Count == 0)
            {
                return default(E);
            }
            return array.GetFirst();
        }
        public E Tail()
        {
            if (Count == 0)
            {
                return default(E);
            }
            return array.GetAt(Count - 1);
        }
        public void Clear()
        {
            array = new LoopingArray<E>();
        }

        public override string ToString()
        {

            return "Queue:font" + array.ToString() + "Trail";
        }

    }
}
